User identification techniques provide data security in a computer network or other communication system by allowing a given user to prove its identity to one or more other system users in the process of communicating with those users. The other system users are thereby assured that they are in fact communicating with the given user. The users may represent individual computers or other types of terminals in the system. A typical user identification process of the "challenge-response" type is initiated when one system user, referred to as the "prover," sends certain information in the form of a commitment to another system user, referred to as the "verifier." Upon receipt of the commitment, the verifier sends a challenge to the prover. The prover utilizes information used to generate the commitment, as well as the challenge and the prover's private key, to generate a response which is sent to the verifier. The verifier uses the commitment, the challenge, the response and a public key to verify that the response was generated by a legitimate prover. The information passed between the prover and verifier is generated in accordance with cryptographic techniques which insure that eavesdroppers or other "attackers" cannot interfere with the identification process.
It is well known that a challenge-response user identification technique can be converted to a digital signature technique by the prover utilizing a one-way hash function to simulate a challenge from a verifier. In such a digital signature technique, a prover generates a commitment, and applies the one-way hash function to it and a message to generate the simulated challenge. The prover then utilizes the simulated challenge, information used to generate the commitment, and a private key to generate a digital signature which is sent along with the message to the verifier. The verifier applies the same one-way hash function during signature verification to recover the simulated challenge, and uses the challenge, the commitment and a public key to validate the signature. As an example of alternative forms of such digital signature schemes, the signature might consist of the challenge and the response from which the commitment and hence the simulated challenge can be recovered. This could then be compared to the challenge included within the signature to test the correctness of the signature.
FIGS. 1A and 1B illustrate two conventional user identification techniques. The notation used to describe the user identification in FIGS. 1A and 1B has been altered relative to the notation of the corresponding cited prior art references for clarity of illustration. FIG. 1A illustrates the operation of an identification technique which involves a prover exponentiating a fixed base a to some randomly-selected power g modulo p and sending it to a verifier, in the manner described in U.S. Pat. No. 4,995,082 and C. P. Schnorr, "Efficient Identification and Signatures for Smart Cards," in G. Brassard, editor, Advances in Cryptology--Crypto '89, Lecture Notes in Computer Science 435, Springer-Verlag, 1990, pp. 239-252. The security of the Schnorr technique relies on the one-way property of the exponentiation function, which makes it difficult for an attacker to compute discrete logarithms with base .alpha. to thereby determine the otherwise unknown power g.
FIG. 1A indicates that in accordance with the Schnorr technique, two prime numbers p and q are chosen at random such that q.vertline.p-1, and a number .alpha. with order q is selected. The numbers p, q and .alpha. are made available to all users. The private key of the prover is a mod q and the public key v of the prover is .alpha..sup.-a mod p. The prover initiates the identification process by selecting a random number g from the set Z.sub.q which consists of the integers {1, . . . ,q-1}. The prover computes the quantity .alpha..sup.g mod p and sends it as a commitment to the verifier. The verifier selects a random number c from the set of integers {1, . . . ,2.sup.t } where t is a security number which depends on the application and in the above-cited article is selected as 72. The verifier sends c as a challenge to the prover. The prover computes a number h corresponding to the quantity g+ac(mod q) as a response, and sends it to the verifier. The verifier accepts the prover as securely identified if cog is found to be congruent modulo p to the quantity .alpha..sup.h v.sup.c.
FIG. 1B illustrates the operation of an identification technique which involves a prover raising a randomly-selected argument g to the power b modulo n and sending it to a verifier, in the manner described in L. C. Guillou and J. J. Quisquater, "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minizing Both Transmission and Memory," in C. G. Gunther, editor, Advances in Cryptology--Eurocrypt '88, Lecture Notes in Computer Science 330, Springer-Verlag, 1988, pp. 123-128. The security of the Guillou-Quisquater technique relies on the difficulty of factoring a product of two large prime numbers. FIG. 1B indicates that in accordance with the Guillou-Quisquater technique, two prime numbers p and q are selected at random, the number n is generated as the product of p and q, and the number b is selected at random. The numbers n and b are made available to all users. The private key of the prover is a mod n and the public key v of the prover is a.sup.-b mod n. The prover initiates the identification process by randomly selecting g from the set Z.sub.n, which consists of the integers {1, . . . ,n-1}. The prover computes the quantity g.sup.b mod n and sends it as a commitment to the verifier. The verifier selects a random number c from the set of integers {1, . . . ,b-1} and sends c as a challenge to the prover. The prover computes a number h corresponding to the quantity ga.sup.c (mod n) as a response, and sends it to the verifier. The verifier accepts the prover as securely identified if g.sup.b is found to be congruent modulo n to h.sup.b v.sup.c.
Although the above-described Schnorr and Guillou-Quisquater techniques can provide acceptable performance in many applications, there is a need for an improved technique which can provide greater computational efficiency than these and other prior art techniques, and which relies for security on features other than the discrete logarithm problem and integer factorization.